Bellman-Ford 算法用来求一个顶点到其他顶点的最短路径，可以处理权值为负数的有向图，但图中不能含有负权回路。
##算法
Bellman-Ford 算法基于一种松弛操作，在不断松弛的过程中，源点到其他每个点的路径值逐渐地得到优化，并最终达到最佳的答案。算法的实质就是反复地（重复|V|-1次）松弛所有的边，最后就可以计算出单源最短路。算法的时间复杂度是O（|V|*|E|），其中 |V| 和 |E| 分别是图的顶点数和边数。
伪代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26//参数：所有点的集合，所有边的集合，源点
function BellmanFord(list vertices, list edges, vertex source)
//需要的变量：
//（u，v）的权值 w
//数组weight[]，源点到每个顶点的最短路
//数组predecessor[]，在最短路中，每个顶点的前继
// Step 1: 对图进行初始化
for each vertex v in vertices:
if v is source then weight[v] := 0
else weight[v] := infinity
predecessor[v] := null
// Step 2: 不断松弛每条边，重复|V|-1次
for i from 1 to size(vertices)-1:
//下面松弛每一条边，可以使用二重循环处理
for each edge (u, v) with weight w in edges:
if weight[u] + w < weight[v]:
weight[v] := weight[u] + w
predecessor[v] := u
// Step 3: 检查是否有负权回路
for each edge (u, v) with weight w in edges:
if weight[u] + w < weight[v]:
error "Graph contains a negative-weight cycle"
return weight[], predecessor[]
简单地说，算法初始化源点的值为0，其他所有节点为无穷大，表示源点到它不可达。
然后对所有的边，如果源点到它的距离可以通过松弛操作缩短，那么距离就更新为新的较小的值。
在每一次（第i次）对所有边松弛操作的过程中，可以找到源点经过i个顶点到达其他顶点的最短路。
因为源点到任意顶点的路径最多经过（|V|-1）个顶点，所以，只要循环|V|-1次就可以计算出所有顶点的最短路。
最后需要判断是否含有负权回路，如果有，则提示无法计算最短路。
##证明
The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
If Distance(u) is not infinity, it is equal to the length of some path from s to u;
If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges.
Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when a vertex’s distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.
For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i−1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges.
If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], …, v[k−1],
v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight
Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight
I.e., every cycle has nonnegative weight.
##检测负权回路
When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman–Ford algorithm can be used for applications in which this is the target to be sought - for example in cycle-cancelling techniques in network flow analysis.
##在路由上的应用
A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:
Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table.
Each node sends its table to all neighboring nodes.
When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes.
The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:
It does not scale well.
Changes in network topology are not reflected quickly since updates are spread node-by-node.
Count to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).
##参考
WIKI